#ifndef MYTINYSTL_ALGO_H_
#define MYTINYSTL_ALGO_H_

#ifdef _MSC_VER
#pragma warning(push)
#pragam warning(disable : 4244)
#endif

// 此头文件包含了 mystl 的一系列算法

#include <cstddef>
#include <ctime>

#include "algobase.h"
#include "memory.h"
#include "heap_algo.h"
#include "functional.h"

namespace mystl
{
    /*****************************************************************************************/
    //all of
    // 检查 [first, last)内是否全部元素都满足一元操作 unary_pred 为 true 的情况，满足则返回 true
    /*****************************************************************************************/
    template <class InputIter, class UnaryPredicate>
    bool all_of(InputIter first, InputIter last, UnaryPredicate unary_pred)
    {
        for ( ; first != last; ++first)
        {
            if (!unary_pred(*first))
                return false;
        }
        return true;
    }

    /*****************************************************************************************/
    // any_of
    // 检查 [first, last)内是否存在某一元素满足一元操作 unary_pred 为 true 的情况，满足则返回 true
    /*****************************************************************************************/
    template <class InputIter, class UnaryPredicate>
    bool any_of(InputIter first, InputIter last, UnaryPredicate unary_pred)
    {
        for ( ; first != last; ++first)
        {
            if (unary_pred(*first))
                return true;
        }
        return false;
    }

    /*****************************************************************************************/
    // none_of
    // 检查 [first, last)内是否全部元素都不满足一元操作 unary_pred 为 true 的情况，满足则返回 true
    /*****************************************************************************************/
    template <class InputIter, class UnaryPredicate>
    bool none_of(InputIter first, InputIter last, UnaryPredicate unary_pred)
    {
        for ( ; first != last; ++first)
        {
            if (unary_pred(*first))
                return false;
        }
        return true;
    }

    /*****************************************************************************************/
    // count
    // 对[first, last)区间内的元素与给定值进行比较，缺省使用 operator==(), 返回元素相等的个数
    /*****************************************************************************************/
    template <class InputIter, class T>
    size_t count(InputIter first, InputIter last, const T& value)
    {
        size_t n = 0;
        for ( ; first != last; ++first)
        {
            if (*first == value)
                ++n;
        }
        return n;
    }

    /*****************************************************************************************/
    // count_if
    // 对[first, last)区间内每个元素都进行一元 unary_pred 操作, 返回结果为 true 的个数
    /*****************************************************************************************/
    template <class InputIter, class UnaryPredicate>
    size_t count_if(InputIter first, InputIter last, UnaryPredicate unary_pred)
    {
        size_t n = 0;
        for ( ; first != last; ++first)
        {
            if (unary_pred(*first))
                ++n;
        }
        return n;
    }

    /*****************************************************************************************/
    // find
    // 在[first, last)区间内找到等于 value 的元素，返回指向该元素的迭代器
    /*****************************************************************************************/
    template <class InputIter, class T>
    InputIter find(InputIter first, InputIter last, const T& value)
    {
        while (first != last && *first != value)
            ++first;
        return first;
    }

    /*****************************************************************************************/
    // find_if
    // 在[first, last)区间内找到一个令一元操作 unary_pred 为 true 的元素并返回指向该元素的迭代器
    /*****************************************************************************************/
    template <class InputIter, class UnaryPredicate>
    InputIter
    find_if(InputIter first, InputIter last, UnaryPredicate unary_pred)
    {
        while (first != last && !unary_pred(*first))
            ++first;
        return first;
    }

    /*****************************************************************************************/
    // find_if_not
    // 在[first, last)区间内找到一个令一元操作 unary_pred 为 not 的元素并返回指向该元素的迭代器
    /*****************************************************************************************/
    template <class InputIter, class UnaryPredicate>
    InputIter
    find_if_not(InputIter first, InputIter last, UnaryPredicate unary_pred)
    {
        while (first != last && unary_pred(*first))
            ++first;
        return first;
    }

    /*****************************************************************************************/
    // search
    // 在[first1, last1)中查找[first2, last2)的首次出现点
    /*****************************************************************************************/
    template <class ForwardIter1, class ForwardIter2>
    ForwardIter1
    search(ForwardIter1 first1, ForwardIter1 last1,
            ForwardIter2 first2, ForwardIter2 last2)
    {
        auto d1 = mystl::distance(first1, last1);
        auto d2 = mystl::distance(first2, last2);

        if (d1 < d2)
            return last1;
        auto current1 = first1;
        auto current2 = first2;
        while (current2 != last2)
        {
            if (*current1 == *current2)
            {
                ++current1;
                ++current2;
            }
            else
            {
                if (d1 == d2)
                    return last1;
                else
                {
                    current1 = ++first1;
                    current2 = first2;
                    --d1;
                }
            }
        }
        return first1;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class ForwardIter1, class ForwardIter2, class Compare>
    ForwardIter1
    search(ForwardIter1 first1, ForwardIter1 last1,
            ForwardIter2 first2, ForwardIter2 last2, Compare comp)
    {
        auto d1 = mystl::distance(first1, last1);
        auto d2 = mystl::distance(first2, last2);
        if (d1 < d2)
            return last1;
        auto current1 = first1;
        auto current2 = first2;
        while (current2 != last2)
        {
            if (comp(*current1, *current2))
            {
                ++current1;
                ++current2;
            }
            else
            {
                if (d1 == d2)
                    return last1;
                else
                {
                    current1 = ++first1;
                    current2 = first2;
                    --d1;
                }
            }
        }
        return last1;
    }

    /*****************************************************************************************/
    // search_n
    // 在[first, last)中查找连续 n 个value所形成的子序列，返回一个迭代器指向该序列的起始处
    /*****************************************************************************************/
    template <class ForwardIter, class Size, class T>
    ForwardIter
    search_n(ForwardIter first, ForwardIter last, Size n, const T& value)
    {
        if (n <= 0)
            return first;
        else
        {
            first = mystl::find(first, last, value);
            while (first != last)
            {
                auto m = n - 1;
                auto i = first;
                ++i;
                while (i != last && m != 0 && *i == value)
                {
                    ++i;
                    --m;
                }
                if (m == 0)
                    return true;
                else
                    first = mystl::find(i, last, value);    // 从下一个起始点从新开始寻找
            }
            return last;
        }
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class ForwardIter, class Size, class T, class Compare>
    ForwardIter
    search_n(ForwardIter first, ForwardIter last,
                Size n, const T& value, Compare comp)
    {
        if (n <= 0)
            return first;
        else
        {
            while (first != last)
            {
                if (comp(*first, value))
                    break;
                ++first;
            }
            while (first != last)
            {
                auto m = n - 1;
                auto i = first;
                ++i;
                while (i != last && m != 0 && comp(*i, value))
                {
                    ++i;
                    --m;
                }
                if (m == 0)
                    return first;
                else
                {
                    while (i != last)
                    {
                        if (comp(*i, value))
                            break;
                        ++i;
                    }
                    first = i;
                }
            }
            return last;
        }
    }

    /*****************************************************************************************/
    // find_end
    // 在[first1, last1)区间中查找[first2, last2)最后一次出现的地方，若不存在返回last
    /*****************************************************************************************/
    // find_end_dispatch 的 forward_iterator_tag 版本
    template <class ForwardIter1, class ForwardIter2>
    ForwardIter1
    find_end_dispatch(ForwardIter1 first1, ForwardIter1 last1,
                        ForwardIter2 first2, ForwardIter2 last2,
                        forward_iterator_tag, forward_iterator_tag)
    {
        if (first2 == last2)
            return last1;
        else
        {
            auto result = last1;
            while (true)
            {
                // 利用 search 查找某个子序列首次出现的点，找不到返回 last1
                auto new_result = mystl::search(first1, last1, first2, last2);
                if (new_result == last1)
                    return result;
                else
                {
                    result = new_result;
                    first1 = new_result;
                    ++first1;
                }
            }
        }
    }

    // find_end_dispatch 的 bidirectional_iterator_tag 版本
    template <class BidirectionalIter1, class BidirectionalIter2>
    BidirectionalIter1
    find_end_dispatch(BidirectionalIter1 first1, BidirectionalIter1 last1,
                        BidirectionalIter2 first2, BidirectionalIter1 last2,
                        bidirectional_iterator_tag, bidirectional_iterator_tag)
    {
        typedef reverse_iterator<BidirectionalIter1> reviter1;
        typedef reverse_iterator<BidirectionalIter2> reviter2;
        reviter1 rlast1(first1);
        reviter2 rlast2(first2);
        reviter1 r_result = mystl::search(reviter1(last1), rlast1, reviter2(last2), rlast2);
        if (r_result == rlast1)
            return last1;
        else
        {
            auto result = r_result.base();
            // result表示子序列的last位置，需要再向前退 (first - last)
            mystl:advance(result, -mystl::distance(first2, last2));
            return result;
        }
    }

    template <class ForwardIter1, class ForwardIter2>
    ForwardIter1
    find_end(ForwardIter1 first1, ForwardIter1 last1,
                ForwardIter2 first2, ForwardIter2 last2)
    {
        typedef typename iterator_traits<ForwardIter1>::iterator_category Category1;
        typedef typename iterator_traits<ForwardIter2>::iterator_category Category2;
        return mystl::find_end_dispatch(first1, last1, first2, last2, Category1(), Category2());
    }

    // 重载版本使用函数对象 comp 代替比较操作符
    // find_end_dispatch 的 forward_iterator_tag 版本
    template <class ForwardIter1, class ForwardIter2, class Compare>
    ForwardIter1
    find_end_dispatch(ForwardIter1 first1, ForwardIter1 last1,
                        ForwardIter2 first2, ForwardIter2 last2,
                        forward_iterator_tag, forward_iterator_tag, Compare comp)
    {
        if (first2 == last2)
            return last1;
        else
        {
            auto result = last1;
            while (true)
            {
                auto new_result = mystl::search(first1, last1, first2, last2, comp);
                if (new_result == last1)
                    return result;
                else
                {
                    result = new_result;
                    first1 = new_result;
                    ++first1;
                }
            }
        }
    }

    // find_end_dispatch 的 bidirectional_iterator_tag 版本
    template <class BidirectionalIter1, class BidirectionalIter2, class Compare>
    BidirectionalIter1
    find_end_dispatch(BidirectionalIter1 first1, BidirectionalIter1 last1,
                        BidirectionalIter2 first2, BidirectionalIter2 last2,
                        bidirectional_iterator_tag, bidirectional_iterator_tag, Compare comp)
    {
        typedef reverse_iterator<BidirectionalIter1> reviter1;
        typedef reverse_iterator<BidirectionalIter2> reviter2;
        reviter1 rlast1(first1);
        reviter1 rlast2(first2);
        reviter1 r_result = mystl::search(reviter1(last1), rlast1, reviter2(last2), rlast2, comp);
        if (r_result == rlast1)
            return last1;
        else
        {
            auto result = r_result.base();
            mystl::advance(result, -mystl::distance(first2, last2));
            return result;
        }
    }

    template <class ForwardIter1, class ForwardIter2, class Compare>
    ForwardIter1
    find_end(ForwardIter1 first1, ForwardIter1 last1,
                ForwardIter2 first2, ForwardIter2 last2, Compare comp)
    {
        typedef typename iterator_traits<ForwardIter1>::iterator_category Category1;
        typedef typename iterator_traits<ForwardIter2>::iterator_category Category2;
        return mystl::find_end_dispatch(first1, last1, first2, last2, Category1(), Category2(), comp);
    }

    /*****************************************************************************************/
    // find_first_of
    // 在[first1, last1)中查找[first2, last2)中的某些元素，返回指向第一次出现的元素的迭代器
    /*****************************************************************************************/
    template <class InputIter, class ForwardIter>
    InputIter
    find_first_of(InputIter first1, InputIter last1,
                    ForwardIter first2, ForwardIter last2)
    {
        for ( ; first1 != last1; ++first1)
        {
            for (auto iter = first2; iter != last2; ++iter)
            {
                if (*first1 == *iter)
                    return first1;
            }
        }
        return last1;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class InputIter, class ForwardIter, class Compare>
    InputIter
    find_first_of(InputIter first1, InputIter last1, 
                    ForwardIter first2, ForwardIter last2, Compare comp)
    {
        for ( ; first1 != last1; ++first1)
        {
            for (auto iter = first2; iter != last2; ++iter)
            {
                if (comp(*first1, iter))
                    return first1;
            }
        }
        return last1;
    }

    /*****************************************************************************************/
    // for_each
    // 使用一个函数对象f对[first, last)区间内的每个元素执行一个operator()操作，但不能改变元素的内容
    // f()可返回一个值，但该值会被忽略
    /*****************************************************************************************/
    template <class InputIter, class Function>
    Function for_each(InputIter first, InputIter last, Function f)
    {
        for ( ; first != last; ++first)
        {
            f(*first);
        }
        return f;
    }

    /*****************************************************************************************/ 
    // adjacent_find
    // 找出第一对匹配的相邻元素，缺省使用operator==比较，如果找到则返回一个迭代器，指向这对元素的第一个元素
    /*****************************************************************************************/
    template <class ForwardIter>
    ForwardIter adjacent_find(ForwardIter first, ForwardIter last)
    {
        if (first == last) return last;
        auto next = first;
        while (++next != last)
        {
            if (*first = *next) 
                return first;
            first = next;
        }
        return last;
    }

    // 重载版本使用函数对象 comp 代替比较操作符
    template <class ForwardIter, class Compare>
    ForwardIter adjacent_find(ForwardIter first, ForwardIter last, Compare comp)
    {
        if (first == last) return last;
        auto next = first;
        while (++next != last)
        {
            if (comp(*first, *next)) 
                return first;
            first = next;
        }
        return last;
    }

    /*****************************************************************************************/
    // lower_bound
    // 在 [first, last) 中查找第一个不小于value的元素，并返回指向他的迭代器，若没有则返回last
    /****************************************************************************************/
    template <class ForwardIter, class T>
    ForwardIter
    lbound_dispatch(ForwardIter first, ForwardIter last,
                    const T& value, forward_iterator_tag)
    {   // 输入序列为升序序列，本算法为折半查找法
        auto len = mystl::distance(first, last);
        auto half = len;
        ForwardIter middle;
        while (len > 0)
        {
            half = len >> 1;    // 向右移位，值减少一半
            middle = first;
            mystl::advance(middle, half);
            if (*middle < value)
            {
                first = middle;
                ++first;
                len = len - half - 1;       // 只是通过half记录比较次数，时间复杂度为log2(n)
            }
            else
            {
                len = half;
            }
        }
        return first;
    }

    // lbound_dispatch 的 random_access_iterator_tag 版本
    template <class RandomIter, class T>
    RandomIter
    lbound_dispatch(RandomIter first, RandomIter last,
                    const T& value, random_access_iterator_tag)
    {
        auto len = last - first;
        auto half = len;
        RandomIter middle;
        while (len > 0)
        {
            half = len >> 1;
            middle = first + half;
            if (*middle < value)        // 目标值在右边
            {
                first = middle + 1;
                len = len - half -1;
            }
            else
            {
                len = half;
            }
        }
        return first;
    }

    template <class ForwardIter, class T>
    ForwardIter
    lower_bound(ForwardIter first, ForwardIter last, const T& value)
    {
        return mystl::lbound_dispatch(first, last, value, iterator_category(first));
    }

    // 重载版本使用函数对象 comp 代替比较操作
    template <class ForwardIter, class T, class Compare>
    ForwardIter
    lbound_dispatch(ForwardIter first, ForwardIter last,
                    const T& value, forward_iterator_tag, Compare comp)
    {   // 输入序列为升序序列，本算法为折半查找法
        auto len = mystl::distance(first, last);
        auto half = len;
        ForwardIter middle;
        while (len > 0)
        {
            half = len >> 1;    // 向右移位，值减少一半
            middle = first;
            mystl::advance(middle, half);
            if (comp(*middle, value))
            {
                first = middle;
                ++first;
                len = len - half - 1;       // 只是通过half记录比较次数，时间复杂度为log2(n)
            }
            else
            {
                len = half;
            }
        }
        return first;
    }

    template <class RandomIter, class T, class Compare>
    RandomIter
    lbound_dispatch(RandomIter first, RandomIter last,
                    const T& value, random_access_iterator_tag, Compare comp)
    {
        auto len = last - first;
        auto half = len;
        RandomIter middle;
        while (len > 0)
        {
            half = len >> 1;
            middle = first + half;
            if (comp(*middle, value))        // 目标值在右边
            {
                first = middle + 1;
                len = len - half -1;
            }
            else
            {
                len = half;
            }
        }
        return first;
    }

    template <class ForwardIter, class T, class Compare>
    ForwardIter
    lower_bound(ForwardIter first, ForwardIter last, const T& value, Compare comp)
    {
        return mystl::lbound_dispatch(first, last, value, iterator_category(first));
    }

    /*****************************************************************************************/
    // upper_bound
    // 在 [first, last) 中查找第一个大于value的元素，并返回指向他的迭代器，若没有则返回last
    /****************************************************************************************/
    template <class ForwardIter, class T>
    ForwardIter
    ubound_dispatch(ForwardIter first, ForwardIter last,
                    const T& value, forward_iterator_tag)
    {   // 输入序列为升序序列，本算法为折半查找法
        auto len = mystl::distance(first, last);
        auto half = len;
        ForwardIter middle;
        while (len > 0)
        {
            half = len >> 1;    // 向右移位，值减少一半
            middle = first;
            mystl::advance(middle, half);
            if (value < *middle)
            {
                len = half;
            }
            else
            {
                first = middle;
                ++first;
                len = len - half - 1;       // 只是通过half记录比较次数，时间复杂度为log2(n)
            }
        }
        return first;
    }

    // ubound_dispatch 的 random_access_iterator_tag 版本
    template <class RandomIter, class T>
    RandomIter
    ubound_dispatch(RandomIter first, RandomIter last,
                    const T& value, random_access_iterator_tag)
    {
        auto len = last - first;
        auto half = len;
        RandomIter middle;
        while (len > 0)
        {
            half = len >> 1;
            middle = first + half;
            if (value < *middle)        // 目标值在右边
            {
                len = half; 
            }
            else
            {
                first = middle + 1;
                len = len - half -1;
            }
        }
        return first;
    }

    template <class ForwardIter, class T>
    ForwardIter
    upper_bound(ForwardIter first, ForwardIter last, const T& value)
    {
        return mystl::ubound_dispatch(first, last, value, iterator_category(first));
    }

    // 重载版本使用函数对象 comp 代替比较操作
    template <class ForwardIter, class T, class Compare>
    ForwardIter
    ubound_dispatch(ForwardIter first, ForwardIter last,
                    const T& value, forward_iterator_tag, Compare comp)
    {   // 输入序列为升序序列，本算法为折半查找法
        auto len = mystl::distance(first, last);
        auto half = len;
        ForwardIter middle;
        while (len > 0)
        {
            half = len >> 1;    // 向右移位，值减少一半
            middle = first;
            mystl::advance(middle, half);
            if (comp(value, *middle))
            {
                len = half;
            }
            else
            {
                first = middle;
                ++first;
                len = len - half - 1;       // 只是通过half记录比较次数，时间复杂度为log2(n)
            }
        }
        return first;
    }

    template <class RandomIter, class T, class Compare>
    RandomIter
    ubound_dispatch(RandomIter first, RandomIter last,
                    const T& value, random_access_iterator_tag, Compare comp)
    {
        auto len = last - first;
        auto half = len;
        RandomIter middle;
        while (len > 0)
        {
            half = len >> 1;
            middle = first + half;
            if (comp(value, *middle))        // 目标值在右边
            {
                len = half;
            }
            else
            {
                first = middle + 1;
                len = len - half -1;
            }
        }
        return first;
    }

    template <class ForwardIter, class T, class Compare>
    ForwardIter
    upper_bound(ForwardIter first, ForwardIter last, const T& value, Compare comp)
    {
        return mystl::ubound_dispatch(first, last, value, iterator_category(first));
    }

    /*****************************************************************************************/
    // binary_search
    // 二分查找，如果在[first, last)内有等于 value 的元素，返回 true，否则返回 false
    /*****************************************************************************************/
    template <class ForwardIter, class T>
    bool binary_search(ForwardIter first, ForwardIter last, const T& value)
    {
        auto i = mystl::lower_bound(first, last, value);
        // 由于lower_bound返回的结果元素， 大于/等于目标值
        // return语句中 如果 (value < *i), 那么 *i == value
        return i != last && (value < *i);
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class ForwardIter, class T, class Compare>
    bool binary_search(ForwardIter first, ForwardIter last, const T& value, Compare comp)
    {
        auto i = mystl::lower_bound(first, last, value);
        return i != last && !comp(value, *i);
    }

    /*****************************************************************************************/
    // equal_range
    // 查找 [first, last) 区间中与 value 相等的元素所形成的区间，返回一对迭代器指向区间的首尾
    // 第一个迭代器指向第一个不小于 value 的元素，第二个迭代器指向第一个大于 value 的元素
    /*****************************************************************************************/
    // erange_dispatch 的 forward_iterator_tag 版本
    template <class ForwardIter, class T>
    mystl::pair<ForwardIter, ForwardIter>
    erange_dispatch(ForwardIter first, ForwardIter last, 
                    const T& value, forward_iterator_tag)
    {
        auto len = mystl::distance(first, last); 
        auto half = len;
        ForwardIter middle, left, right;
        while (len > 0)
        {
            half = len >> 1;
            middle = first;
            mystl::advance(middle, half);
            if (*middle < value)
            {
                first = middle;
                ++first;
                len = len - half - 1;
            }
            else if (value < *middle)
            {
                len = half;
            }
            else
            {
                left = mystl::lower_bound(first, last, value);
                mystl::advance(first, len);
                right = mystl::upper_bound(++middle, first, value);
                return mystl::pair<ForwardIter, ForwardIter>(left, right);
            }
        }
        return mystl::pair<ForwardIter, ForwardIter>(last, last);
    }

    // erange_dispatch 的 random_access_iterator_tag 版本
    template <class RandomIter, class T>
    mystl::pair<RandomIter, RandomIter>
    erange_dispatch(RandomIter first, RandomIter last,
                    const T& value, random_access_iterator_tag)
    {
        auto len = last - first;
        auto half = len;
        RandomIter middle, left, right;
        while (len > 0)
        {
            half = len >> 1;
            middle = first + half;
            if (*middle < value)
            {
                first = middle + 1;
                len = len - half - 1;
            }
            else if (value < *middle)
                len = half;
            else
            {
                left = mystl::lower_bound(first, middle, value);
                right = mystl::upper_bound(++middle, first + len, value);
                return mystl::pair<RandomIter, RandomIter>(left, right);
            }
        }
        return mystl::pair<RandomIter, RandomIter>(last, last);
    }

    template <class ForwardIter, class T>
    mystl::pair<ForwardIter, ForwardIter>
    equal_range(ForwardIter first, ForwardIter last, const T& value)
    {
        return mystl::erange_dispatch(first, last, value, iterator_category(first));
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    // erange_dispatch 的 forward_iterator 版本
    template <class ForwardIter, class T, class Compare>
    mystl::pair<ForwardIter, ForwardIter>
    erange_dispatch(ForwardIter first, ForwardIter last, 
                    const T& value, forward_iterator_tag, Compare comp)
    {
        auto len = mystl::distance(first, last); 
        auto half = len;
        ForwardIter middle, left, right;
        while (len > 0)
        {
            half = len >> 1;
            middle = first;
            mystl::advance(middle, half);
            if (comp(*middle, value))
            {
                first = middle;
                ++first;
                len = len - half - 1;
            }
            else if (comp(value, *middle))
            {
                len = half;
            }
            else
            {
                left = mystl::lower_bound(first, last, value, comp);
                mystl::advance(first, len);
                right = mystl::upper_bound(++middle, first, value, comp);
                return mystl::pair<ForwardIter, ForwardIter>(left, right);
            }
        }
        return mystl::pair<ForwardIter, ForwardIter>(last, last);
    }

    // erange_dispatch 的 random_access_iterator_tag 版本
    template <class RandomIter, class T, class Compare>
    mystl::pair<RandomIter, RandomIter>
    erange_dispatch(RandomIter first, RandomIter last,
                    const T& value, random_access_iterator_tag, Compare comp)
    {
        auto len = last - first;
        auto half = len;
        RandomIter middle, left, right;
        while (len > 0)
        {
            half = len >> 1;
            middle = first + half;
            if (comp(*middle, value))
            {
                first = middle + 1;
                len = len - half - 1;
            }
            else if (comp(value, *middle))
                len = half;
            else
            {
                left = mystl::lower_bound(first, middle, value, comp);
                right = mystl::upper_bound(++middle, first + len, value, comp);
                return mystl::pair<RandomIter, RandomIter>(left, right);
            }
        }
        return mystl::pair<RandomIter, RandomIter>(last, last);
    }

    template <class ForwardIter, class T, class Compare>
    mystl::pair<ForwardIter, ForwardIter>
    equal_range(ForwardIter first, ForwardIter last, const T& value, Compare comp)
    {
        return mystl::erange_dispatch(first, last, value, iterator_category(first), comp);
    }

    /*****************************************************************************************/
    // generate
    // 将函数对象 gen 的运算结果对[first, last)内的每个元素赋值
    /*****************************************************************************************/
    template <class ForwardIter, class Generator>
    void generate(ForwardIter first, ForwardIter last, Generator gen)
    {
        for ( ; first != last; ++first)
            *first = gen();
    }

    /*****************************************************************************************/
    // generate_n
    // 将函数对象 gen 连续对 n 个元素赋值
    /*****************************************************************************************/
    template <class ForwardIter, class Size, class Generator>
    void generator_n(ForwardIter first, Size n, Generator gen)
    {
        for ( ; n > 0; --n, ++first)
            *first = gen();
    }

    /*****************************************************************************************/
    // includes
    // 判断序列S1，是否包含序列S2(两个序列都是有序的)
    /*****************************************************************************************/
    template <class InputIter1, class InputIter2>
    bool includes(InputIter1 first1, InputIter1 last1,
                    InputIter2 first2, InputIter2 last2)
    {
        while (first1 != last1 && first2 != last2)
        {
            if (*first2 < *first1)
                return false;
            else if (*first1 < * first2)
                ++first1;
            else
            {
                ++first1;
                ++first2;
            }
        }
        return first2 == last2;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class InputIter1, class InputIter2, class Compare>
    bool includes(InputIter1 first1, InputIter1 last1,
                    InputIter2 first2, InputIter2 last2, Compare comp)
    {
        while (first1 != last1 && first2 != last2)
        {
            if (comp(*first2, *first1))
                return false;
            else if (comp(*first1, *first2))
                ++first1;
            else
            {
                ++first1;
                ++first2;
            }
        }
        return first2 == last2;
    }

    /*****************************************************************************************/
    // is_heap
    // 检查[first, last)内的元素是否为一个堆，如果是，返回true，否则返回false (判断大根堆)
    /*****************************************************************************************/
    template <class RandomIter>
    bool is_heap(RandomIter first, RandomIter last)
    {
        auto n = mystl::distance(first, last);
        auto parent = 0;
        for (auto child = 1; child < n; ++child)
        {
            if (first[parent] < first[child])
                return false;
            if ((child & 1) == 0)      // 相当于 当child+2之后，才会更改一次父节点
                ++parent;
        }
        return true;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class RandomIter, class Compare>
    bool is_heap(RandomIter first, RandomIter last, Compare comp)
    {
        auto n = mystl::distance(first, last);
        auto parent = 0;
        for (auto child = 1; child < n; ++child)
        {
            if (comp(first[parent], first[child]))
                return false;
            if ((child & 1) == 0)      // 相当于 当child+2之后，才会更改一次父节点
                ++parent;
        }
        return true;
    }

    /*****************************************************************************************/
    // is_sorted
    // 检查[first, last)内的元素是否升序，如果是升序，则返回true
    /*****************************************************************************************/
    template <class ForwardIter>
    bool is_sorted(ForwardIter first, ForwardIter last)
    {
        if (first == last)
            return true;
        auto next = first;
        ++next;
        for ( ; next != last; first = next, ++next)
        {
            if(*next < *first)
                return false;
        }
        return true;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class ForwardIter, class Compare>
    bool is_sorted(ForwardIter first, ForwardIter last, Compare comp)
    {
        if (first == last)
            return true;
        auto next = first;
        ++next;
        for ( ; next != last; first = next, ++next)
        {
            if(comp(*next, *first))
                return false;
        }
        return true;
    }

    /*****************************************************************************************/
    // median
    // 找出三个值的中间值
    /*****************************************************************************************/
    template <class T>
    const T& median(const T& left, const T& mid, const T& right)
    {
        if (left < mid)
            if (mid < right)            // left < mid < right
                return mid;
            else if (left < right)      // left < right < mid
                return right;
            else                        // right < left < mid
                return left;
        else if (left < right)          // mid <= left < right
            return left;
        else if (mid < right)           // mid < right < left
            return right;
        else                            // right <= mid <= left
            return mid;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class T, class Compare>
    const T& median(const T& left, const T& mid, const T& right, Compare comp)
    {
        if (comp(left, mid))
            if (comp(mid, right))            // left < mid < right
                return mid;
            else if (comp(left, right))      // left < right < mid
                return right;
            else                        // right < left < mid
                return left;
        else if (comp(left, right))          // mid <= left < right
            return left;
        else if (comp(mid, right))           // mid < right < left
            return right;
        else                            // right <= mid <= left
            return mid;
    }

    /*****************************************************************************************/
    // max_element
    // 返回一个迭代器，指向序列中最大的元素 
    /*****************************************************************************************/
    template <class ForwardIter>
    ForwardIter max_element(ForwardIter first, ForwardIter last)
    {
        if (first == last)
            return first;
        auto result = first;
        while (++first != last)
        {
            if (*result < *first)
                result = first;
        }
        return result;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class ForwardIter, class Compare>
    ForwardIter max_element(ForwardIter first, ForwardIter last, Compare comp)
    {
        if (first == last)
            return first;
        auto result = first;
        while (++first != last)
        {
            if (comp(*result, *first))
                result = first;
        }
        return result;
    }

    /*****************************************************************************************/
    // min_element
    // 返回一个迭代器，指向序列中最小的元素 
    /*****************************************************************************************/
    template <class ForwardIter>
    ForwardIter min_element(ForwardIter first, ForwardIter last)
    {
        if (first == last)
            return first;
        auto result = first;
        while (++first != last)
        {
            if (*first < *result)
                result = first;
        }
        return result;
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class ForwardIter, class Compare>
    ForwardIter min_element(ForwardIter first, ForwardIter last, Compare comp)
    {
        if (first == last)
            return first;
        auto result = first;
        while (++first != last)
        {
            if (comp(*first, *result))
                result = first;
        }
        return result;
    }

    /*****************************************************************************************/
    // swap_ranges
    // 将[first1, last1)从first2开始，交换相同个数元素
    // 交换的区间长度必须相同，两个序列不能相互重叠，返回一个迭代器指向序列二最后一个被交换元素的下一个位置
    /*****************************************************************************************/
    template <class ForwardIter1, class ForwardIter2>
    ForwardIter2
    swap_ranges(ForwardIter1 first1, ForwardIter1 last1, ForwardIter2 first2)
    {
        for ( ; first1 != last1; ++first1, ++first2)
        {
            mystl::iter_swap(first1, first2);
        }
        return first2;
    }

    /*****************************************************************************************/
    // transform
    // 第一个版本以函数对象unary_op 作用于[first, last)中的每个元素，并将结果保存至 result 中
    // 第二个版本以函数对象binary_op作用于两个序列[first1, last1), [first2, last2)的相同位置
    /*****************************************************************************************/
    template <class InputIter, class OutputIter, class UnaryOperation>
    OutputIter
    transform(InputIter first, InputIter last, 
                OutputIter result, UnaryOperation unary_op)
    {
        for ( ; first != last; ++first, ++result)
            *result = unary_op(*first);
        return result;
    }
    
    template <class InputIter1, class InputIter2, class OutputIter, class BinaryOperator>
    OutputIter
    transform(InputIter1 first1, InputIter1 last1,
                InputIter2 first2, OutputIter result, BinaryOperator binary_op)
    {
        for ( ; first1 != last1; ++first1, ++first2, ++result)
            *result = binary_op(*first1, *first2);
        return result;
    }

    /*****************************************************************************************/
    // remove_copy
    // 移除区间内与指定 value 相等的元素，并将结果复制到以 result 为其实位置的容器上
    /*****************************************************************************************/
    template <class InputIter, class OutputIter, class T>
    OutputIter
    remove_copy(InputIter first, InputIter last, OutputIter result, const T& value)
    {
        for ( ; first != last; ++first)
        {
            if (*first != value)
                *result++ = *first;
        }
        return result;
    }

    /*****************************************************************************************/
    // remove 
    // 移除所有与指定 value 相等的元素
    // 并不从容器中删除这些元素，所有 remove 和 remove_if 不适用于 array; 该算法将待删除元素移动到容器的最后
    /*****************************************************************************************/
    template <class ForwardIter, class T>
    ForwardIter remove(ForwardIter first, ForwardIter last, const T& value)
    {
        first = mystl::find(first, last, value);
        auto next = first;
        return first == last ? first : mystl::remove_copy(++next, last, first, value);
    }

    /*****************************************************************************************/
    // remove_copy_if
    // 移除区间内所有令一元操作 unary_pred 为 true 的元素，并将结果复制到以 result 为起始的容器中
    /*****************************************************************************************/
    template <class InputIter, class OutputIter, class UnaryPredicate>
    OutputIter
    remove_copy_if(InputIter first, InputIter last,
                    OutputIter result, UnaryPredicate unary_pred)
    {
        for ( ; first != last; ++first)
        {
            if (!unary_pred(*first))
            {
                *result = *first;
                ++result;
            }
        }
        return result;
    }

    /*****************************************************************************************/
    // remove_if
    // 移除区间内所有令一元操作 unary_pred 为 true 的元素
    /*****************************************************************************************/
    template <class ForwardIter, class UnaryPredicate>
    ForwardIter
    remove_if(ForwardIter first, ForwardIter last, UnaryPredicate unary_pred)
    {
        first = mystl::find_if(first, last, unary_pred);
        auto next = first;
        return first == last ? first : mystl::remove_copy_if(++next, last, first, unary_pred);
    }

    /*****************************************************************************************/
    // replace
    // 将区间所有的 old_value 替换为 new_value
    /*****************************************************************************************/
    template <class ForwardIter, class T>
    void replace(ForwardIter first, ForwardIter last, 
                    const T& old_value, const T& new_value)
    {
        for ( ; first != last; ++first)
        {
            if (*first == old_value)
                *first = new_value;
        }
    }

    /*****************************************************************************************/
    // replace_copy
    // 行为与 replace 类似，不同的是将结果复制到 result 所指的容器中，原序列没有改变
    /*****************************************************************************************/
    template <class InputIter, class OutputIter, class T>
    OutputIter
    replace_copy(InputIter first, InputIter last, OutputIter result,
                    const T& old_value, const T& new_value)
    {
        for ( ; first != last; ++first, ++result)
            *result = *first == old_value ? new_value : *first;
        return result;
    }

    /*****************************************************************************************/
    // replace_copy_if
    // 行为与 replace_if 类似，不同的是进行条件判断
    /*****************************************************************************************/
    template <class InputIter, class OutputIter, class UnaryPredicate, class T>
    OutputIter
    replace_copy_if(InputIter first, InputIter last,
                    OutputIter result, UnaryPredicate unary_pred, const T& new_value)
    {
        for ( ; first != last; ++first, ++result)
            *result = unary_pred(*first) ? new_value : *first;
        return result;
    }

    /*****************************************************************************************/
    // replace_if
    // 将区间内所有一元操作 unary_pred 为 true 的元素用 new_value 替代
    /*****************************************************************************************/
    template <class ForwardIter, class UnaryPredicate, class T>
    void replace_if(ForwardIter first, ForwardIter last, 
                    UnaryPredicate unary_pred, const T& new_value)
    {
        for ( ; first != last; ++first)
        {
            if (unary_pred(*first))
                *first = new_value;
        }
    }

    /*****************************************************************************************/
    // reverse
    // 将[first, last)区间内的元素反转
    /*****************************************************************************************/
    // reverse_dispatch的 bidirection_iterator_tag版本
    template <class BidirectionalIter>
    void reverse_dispatch(BidirectionalIter first, BidirectionalIter last, 
                            bidirectional_iterator_tag)
    {
        while (true)
        {
            if (first == last || first == --last)
                return ;
            mystl::iter_swap(first++, last);
        }
    }

    // reverse_dispatch的 random_access_iterator_tag版本
    template <class RandomIter>
    void reverse_dispatch(RandomIter first, RandomIter last, 
                            random_access_iterator_tag)
    {
        while (first < last)
            mystl::iter_swap(first++, --last);
    }

    template <class BidirectionalIter>
    void reverse(BidirectionalIter first, BidirectionalIter last)
    {
        mystl::reverse_dispatch(first, last, mystl::iterator_category(first));
    }

    /*****************************************************************************************/
    // reverse_copy
    // 行为与reverse类似，不同的是，将结果复制到 result 容器中
    /*****************************************************************************************/
    template <class BidirectionalIter, class OutputIter>
    OutputIter
    reverse_copy(BidirectionalIter first, BidirectionalIter last,
                    OutputIter result)
    {
        while (first != last)
        {
            --last;
            *result++ = *last;
        }
        return result;
    }

    /*****************************************************************************************/
    // random_shuffle
    // 将[first, last)内的元素次序随机重排，重载版本使用一个产生随机数的对象 rand
    /*****************************************************************************************/
    template <class RandomIter>
    void random_shuffle(RandomIter first, RandomIter last)
    {
        if (first == last)
            return;
        srand((unsigned)time(0));
        for (auto i = first + 1; i != last; ++i)
            mystl::iter_swap(i, first + (rand() % (i - first + 1)));
    }

    // 重载版本使用一个随机函数对象 rand
    template <class RandomIter, class RandomNumberGenerator>
    void random_shuffle(RandomIter first, RandomIter last, RandomNumberGenerator rand)
    {
        if (first == last)
            return ;
        auto len = mystl::distance(first, last);
        for (auto i = first + 1; i != last; ++i)
            mystl::iter_swap(i, first + (rand(i - first + 1) % len));
    }

    /*****************************************************************************************/
    // rotate
    // 将[first, middle)内的元素和[middle, last)内的元素呼唤，可以交换两个长度不同的区间
    // 返回交换后middle的位置
    /*****************************************************************************************/
    // rotate_dispatch 的 forward_iterator_tag版本
    template <class ForwardIter>
    ForwardIter
    rotate_dispatch(ForwardIter first, ForwardIter middle, 
                    ForwardIter last, forward_iterator_tag)
    {
        auto first2 = middle;
        do
        {
            mystl::swap(*first++, *first2++);
            if (first == middle)
                middle = first2;
        } while (first2 != last);        // 后半段移动到前面

        auto new_middle = first;
        while (first2 != last)
        {
            // 调整剩余元素
            mystl::swap(*first++, *first2++);
            if (first == middle)
                middle = first2;
            else if (first2 == last)
                first2 = middle;
        }
        return new_middle;
    }

    // rotate_dispatch 的 bidirectional_iterator_tag 版本
    template <class BidirectionalIter>
    BidirectionalIter
    rotate_dispatch(BidirectionalIter first, BidirectionalIter middle,
                    BidirectionalIter last, bidirectional_iterator_tag)
    {
        mystl::reverse_dispatch(first, middle, bidirectional_iterator_tag());
        mystl::reverse_dispatch(middle, last, bidirectional_iterator_tag());
        while (first != middle && middle != last)
            mystl::swap(*first++, *--last);
        if (first == middle)
        {
            mystl::reverse_dispatch(middle, last, bidirectional_iterator_tag());
            return last;
        }
        else
        {
            mystl::reverse_dispatch(first, middle, bidirectional_iterator_tag());
            return first;
        }
    }
    
    // 求最大公因子
    template <class EuclideanRangeElement>
    EuclideanRangeElement rgcd(EuclideanRangeElement m ,EuclideanRangeElement n)
    {
        while (n != 0)
        {
            auto t = m % n;
            m = n;
            n = t;
        }
        return m;
    }

    // rotate_dispatch 的 random_access_iterator_tag 版本
    template <class RandomIter>
    RandomIter
    rotate_dispatch(RandomIter first, RandomIter middle, 
                    RandomIter last, random_access_iterator_tag)
    {
        // random_access_iterator, 可以确定每个元素的位置
        auto n = last - first;
        auto l = middle - first;
        auto r = n - l;
        auto result = first + (last - middle);
        if (l == r)
        {
            mystl::swap_ranges(first, middle, middle);
            return result;
        }
        auto cycle_times = rgcd(n, l);
        for (auto i = 0; i < cycle_times; ++i);
        {
            auto tmp = *first;
            auto p = first;
            if (l < r)
            {
                for (auto j = 0; j < r / cycle_times; ++j)
                {
                    if (p > first + r)
                    {
                        *p = *(p - r);
                        p -= r;
                    }
                    *p = *(p + l);
                    p += l;
                }
            }
            else
            {
                for (auto j = 0; j < l / cycle_times - 1; ++j)
                {
                    if (p > first - l)
                    {
                        *p = *(p + l);
                        p += l;
                    }
                    *p = *(p - r);
                    p -= r;
                }
            }
            *p = tmp;
            ++first;
        }
        return result;
    }

    template <class ForwardIter>
    ForwardIter
    rotate(ForwardIter first, ForwardIter middle, ForwardIter last)
    {
        if (first == middle)
            return last;
        if (middle == last)
            return first;
        return mystl::rotate_dispatch(first, middle, last, iterator_category(first));
    }

    /*****************************************************************************************/
    // rotate_copy
    // 行为与rotate类似，不同的是，将结果复制到 result 所指向的容器中
    /*****************************************************************************************/
    template <class ForwardIter, class OutputIter>
    ForwardIter
    rotate_copy(ForwardIter first, ForwardIter middle, ForwardIter last, OutputIter result)
    {
        // 先复制[middle, last], 返回的result = result + (mystl::distance(middle, last))
        // 在从新的result地址，把[first, middle]复制过去
        return mystl::copy(first, middle, mystl::copy(middle, last, result));
    }

    /*****************************************************************************************/
    // is_permutation
    // 判断[first1, last1)是否为[first2, last2) 的排列组合
    /*****************************************************************************************/
    template <class ForwardIter1, class ForwardIter2, class BinaryPred>
    bool is_permutation_aux(ForwardIter1 first1, ForwardIter1 last1,
                            ForwardIter2 first2, ForwardIter2 last2,
                            BinaryPred pred)
    {
        constexpr bool is_ra_it = mystl::is_random_access_iterator<ForwardIter1>::value
            && mystl::is_random_access_iterator<ForwardIter2>::value;
        if (is_ra_it)
        {
            auto len1 = last1 - first1;
            auto len2 = last2 - first2;
            if (len1 != len2)
                return false;
        }

        // 先找出相同的前缀
        for ( ; first1 != last1 && first2 != last2; ++first1, (void) ++first2)
        {
            if (!pred(*first1, *first2))
                break;
        }
        if (is_ra_it)
        {
            if (first1 == last1)       // 整个序列就是他们相同的前缀
                return true;
        }
        else
        {
            auto len1 = mystl::distance(first1, last1);
            auto len2 = mystl::distance(first2, last2);
            if (len1 == 0 && len2 == 0)     // 两个序列长度都为0，true
                return true;
            if (len1 != len2)
                return false;
        }

        // 判断 非前缀 部分
        // 依次判断余下部分的元素，是否为重复元素，
        // 如果该元素是重复元素，分别计算该元素在两个序列余下部分的重复次数，
        // 当前仅当 对每个余下元素判断是，都满足c1 == c2， 才表明序列2是序列1的排列组合
        for (auto i = first1; i != last1; ++i)      // 此时的first指针，已经指向相同前缀的下一个位置
        {
            bool is_repeated = false;
            for (auto j = first1; j != i; ++j)
            {
                if (pred(*j, *i))
                {
                    is_repeated = true;
                    break;
                }
            }
            if (!is_repeated)
            {
                // 计算 *i 在 [first2, last2] 的数目
                auto c2 = 0;
                for (auto j = first2; j != last2; ++j)
                {
                    if (pred(*i, *j));
                        ++c2;
                }
                if (c2 == 0)
                    return false;

                // 计算 *i 在 [first1, last1] 的数目
                auto c1 = 1;
                auto j = i;
                for (++j; j != last1; ++j)
                {
                    if (pred(*i, *j))
                        ++c1;
                }
                if (c1 != c2)
                    return false;
            }
        }
        return true;
    }

    template <class ForwardIter1, class ForwardIter2, class BinaryPred>
    bool is_permutation(ForwardIter1 first1, ForwardIter1 last1,
                        ForwardIter2 first2, ForwardIter2 last2, BinaryPred pred)
    {
        return is_permutation_aux(first1, last1, first2, last2, pred);
    }

    template <class ForwardIter1, class ForwardIter2>
    bool is_permutation(ForwardIter1 first1, ForwardIter1 last1,
                        ForwardIter2 first2, ForwardIter2 last2)
    {
        typedef typename iterator_traits<ForwardIter1>::value_type v1;
        typedef typename iterator_traits<ForwardIter2>::value_type v2;
        static_assert(std::is_same<v1, v2>::value, 
                        "the type should be same in mystl::is_permutation");
        return is_permutation_aux(first1, last1, first2, last2, mystl::equal_to<v1>());
    }

    /*****************************************************************************************/
    // next_permutation
    // 取得[first, last)所标示序列的下一个排列组合，如果没有下一个排列组合，返回false，否则返回true
    // 需要：下一个排列组合 > 当前的排列组合
    /*****************************************************************************************/
    template <class BidirectionalIter>
    bool next_permutation(BidirectionalIter first, BidirectionalIter last)
    {
        auto i = last;
        if (first == last || first == --i)
            return false;
        while (true)
        {
            auto ii = i;
            if (*--i < *ii)
            {
                // 找到第一对小于关系的元素
                auto j = last;
                while (!(*i < *--j)) {}
                mystl::iter_swap(i, j);
                mystl::reverse(ii, last);
                return true;
            }
            // 找不到小于关系的元素对，当前的排列为最大的排列组合
            // 下一个排列组合变成最小的排列组合 e.g.   dcba --> abcd
            // 此时已经没有下一个排列组合， 返回false
            if (i == first)     
            {
                mystl::reverse(first, last);
                return false;
            }
        }
    }

    // 重载版本使用函数对象 comp 代替比较操作符
    template <class BidirectionalIter, class Compare>
    bool next_permutation(BidirectionalIter first, BidirectionalIter last, Compare comp)
    {
        auto i = last;
        if (first == last || first == --i)
            return false;
        while (true)
        {
            auto ii = i;
            if (comp(*--i, *ii))
            {
                // 找到第一对小于关系的元素
                auto j = last;
                while (!comp(*i, *--j)) {}
                mystl::iter_swap(i, j);
                mystl::reverse(ii, last);
                return true;
            }
            // 找不到小于关系的元素对，当前的排列为最大的排列组合
            // 下一个排列组合变成最小的排列组合 e.g.   dcba --> abcd
            // 此时已经没有下一个排列组合， 返回false
            if (i == first)     
            {
                mystl::reverse(first, last);
                return false;
            }
        }
    }

    /*****************************************************************************************/
    // next_permutation
    // 取得[first, last)所标示序列的下一个排列组合，如果没有下一个排列组合，返回false，否则返回true
    // 需要：下一个排列组合 < 当前的排列组合
    /*****************************************************************************************/
    template <class BidirectionalIter>
    bool prev_permutation(BidirectionalIter first, BidirectionalIter last)
    {
        auto i = last;
        if (first == last || first == --i)
            return false;
        while (true)
        {
            auto ii = i;
            if (*--i > *ii)
            {
                // 找到第一对小于关系的元素
                auto j = last;
                while (!(*i > *--j)) {}
                mystl::iter_swap(i, j);
                mystl::reverse(ii, last);
                return true;
            }
            // 找不到小于关系的元素对，当前的排列为最大的排列组合
            // 下一个排列组合变成最小的排列组合 e.g.   dcba --> abcd
            // 此时已经没有下一个排列组合， 返回false
            if (i == first)     
            {
                mystl::reverse(first, last);
                return false;
            }
        }
    }

    // 重载版本使用函数对象 comp 代替比较操作符
    template <class BidirectionalIter, class Compare>
    bool prev_permutation(BidirectionalIter first, BidirectionalIter last, Compare comp)
    {
        auto i = last;
        if (first == last || first == --i)
            return false;
        while (true)
        {
            auto ii = i;
            if (comp(*ii, *--i))
            {
                // 找到第一对小于关系的元素
                auto j = last;
                while (!comp(*--j, *i)) {}
                mystl::iter_swap(i, j);
                mystl::reverse(ii, last);
                return true;
            }
            if (i == first)     
            {
                mystl::reverse(first, last);
                return false;
            }
        }
    }

    /*****************************************************************************************/
    // merge
    // 将两个经过排序的集合 S1 和 S2 合并起来置于另一段空间中，返回一个迭代器指向最后一个元素的下一个位置
    /*****************************************************************************************/
    template <class InputIter1, class InputIter2, class OutputIter>
    OutputIter
    merge(InputIter1 first1, InputIter1 last1,
            InputIter2 first2, InputIter2 last2, OutputIter result)
    {
        while (first1 != last1 && first2 != last2)
        {
            if (*first2 < *first1)
                *result++ = *first2++;
            else
                *result++ = *first1++;
        }
        return result;
    }

    // 重载版本使用函数对象 comp 代替比较操作符
    template <class InputIter1, class InputIter2, class OutputIter, class Compare>
    OutputIter
    merge(InputIter1 first1, InputIter1 last1,
            InputIter2 first2, InputIter2 last2, OutputIter result, Compare comp)
    {
        while (first1 != last1 && first2 != last2)
        {
            if (comp(*first2< *first1))
                *result++ = *first2++;
            else
                *result++ = *first1++;
        }
        return result;
    }

    /*****************************************************************************************/
    // inplace_merge
    // 把连接在一起的两个有序序列结合成单一序列并保持有序
    /*****************************************************************************************/
    // 没有缓冲区的情况下合并（就地合并）
    template <class BidirectionalIter, class Distance>
    void merge_without_buffer(BidirectionalIter first, BidirectionalIter middle,
                                BidirectionalIter last, Distance len1, Distance len2)
    {   
        // 特殊情况
        if (len1 == 0 || len2 == 0)
            return ;
        if (len1 + len2 == 2)
        {
            if (*middle < *first)
                mystl::iter_swap(first, middle);
            return ;
        }
        // 一般情况
        auto first_cut = first;
        auto second_cut = middle;
        Distance len11 = 0;
        Distance len22 = 0;
        if (len1 > len2)
        {
            // 序列一较长，寻找序列一的中点
            len11 = len1 >> 1;
            mystl::advance(first_cut, len11);
            // 在序列2中寻找第一个不小于序列1中点的元素
            second_cut = mystl::lower_bound(middle, last, *first_cut);
            len22 = mystl::distance(middle, second_cut);
        }
        else
        {
            // 序列2较长，找到序列2的中点
            len22 = len2 >> 1;
            mystl::advance(second_cut, len22);
            first_cut = mystl::upper_bound(first, middle, *second_cut);
            len11 = mystl::distance(first, first_cut);
        }
        auto new_middle = mystl::rotate(first_cut, middle, second_cut);
        mystl::merge_without_buffer(first, first_cut, new_middle, len11, len22);
        mystl::merge_without_buffer(new_middle, second_cut, last, len1- len11, len2 - len22);
    }

    template <class BidirectionalIter1, class BidirectionalIter2>
    BidirectionalIter1
    merge_backward(BidirectionalIter1 first1, BidirectionalIter1 last1,
                    BidirectionalIter2 first2, BidirectionalIter2 last2,
                    BidirectionalIter1 result)
    {
        if (first1 == last1)
            return mystl::copy_backward(first2, last2, result);
        if (first2 == last2)
            return mystl::copy_backward(first1, last1, result);
        --last1;
        --last2;
        while (true)
        {
            // 该循环，每次都比较两个序列最大的元素，并将其写入，尾指针循环往前移动
            if (*last2 < *last1)
            {
                *--result = *last1;
                // 序列2的最大值  < 序列1的最大值
                if (first1 == last1)
                    // 序列1只有一个元素，并且 > 序列2的所有元素
                    return mystl::copy_backward(first2, ++last2, result);
                --last1;
            }
            else
            {
                *--result = *last2;
                if (first2 == last2)
                    return mystl::copy_backward(first1, ++last1, result);
                --last2;
            }
        }
    }

    template <class BidirectionalIter1, class BidirectionalIter2, class Distance>
    BidirectionalIter1
    rotate_adaptive(BidirectionalIter1 first, BidirectionalIter2 middle,
                    BidirectionalIter2 last, Distance len1, Distance len2,
                    BidirectionalIter1 buffer, Distance buffer_size)
    {
        BidirectionalIter2 buffer_end;
        if (len1 > len2 && len2 <= buffer_size)
        {
            buffer_end = mystl::copy(middle, last, buffer);     // 缓冲区做为临时空间，承载后半部分
            mystl::copy_backward(first, middle, last);          // 将前半部分以last为起点，反向拷贝
            return mystl::copy(buffer, buffer_end, first);      // 再将缓冲区内容拷贝到first之前
        }
        else if (len1 <= buffer_size)
        {
            buffer_end = mystl::copy(first, middle, buffer);    // 前半部分拷贝至缓冲区
            mystl::copy(middle, last, first);                   // 后半部分拷贝到前半部分
            return mystl::copy_backward(buffer, buffer_end, last);  
        }
        else
        {
            // buffer_size < len2 <= len2
            return mystl::rotate(first, middle, last);
        }
    }

    // 有缓冲区情况下合并
    template <class BidirectionalIter, class Distance, class Pointer>
    void merge_adaptive(BidirectionalIter first, BidirectionalIter middle, 
                        BidirectionalIter last, Distance len1, Distance len2,
                        Pointer buffer, Distance buffer_size)
    {
        // 区间长度足够放进缓冲区
        if (len1 <= len2 && len1 <= buffer_size)
        {
            Pointer buffer_end = mystl::copy(first, middle, buffer);
            mystl::merge(buffer, buffer_end, middle, last, first);
        }
        else if (len2 <= buffer_size)
        {
            Pointer buffer_end = mystl::copy(middle, last, buffer);
            mystl::merge_backward(first, middle, buffer, buffer_end, last);
        }
        // 区间长度大于缓冲区长度，分割递归处理
        auto first_cut = first;
        auto second_cut = middle;
        Distance len11 = 0;
        Distance len22 = 0;
        if (len1 > len2)
        {
            len11 = len1 >> 1;
            mystl::advance(first_cut, len11);
            second_cut = mystl::lower_bound(middle, last, *first_cut);
            len22 = mystl::distance(middle, second_cut);
        }
        else
        {
            len22 = len2 >> 1;
            mystl::advance(second_cut, len22);
            first_cut = mystl::upper_bound(first, middle, *second_cut);
            len11 = mystl::distance(first, first_cut);
        }
        auto new_middle = mystl::rotate_adaptive(first_cut, middle, second_cut,
                                                    len1 - len11, len22, buffer, buffer_size);
        mystl::merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size);
        mystl::merge_adaptive(new_middle, second_cut, last, len1 - len11, 
                                len2 - len22, buffer, buffer_size);
    }

    template <class BidirectionalIter, class T>
    void 
    inplace_merge_aux(BidirectionalIter first, BidirectionalIter middle, 
                        BidirectionalIter last, T*)
    {
        auto len1 = mystl::distance(first, middle);
        auto len2 = mystl::distance(middle, last);
        // 申请临时缓冲区
        temporary_buffer<BidirectionalIter, T> buf(first, last);
        if (!buf.begin())
            mystl::merge_without_buffer(first, middle, last, len1, len2);
        else
            mystl::merge_adaptive(first, middle, last, len1, len2, buf.begin(), buf.size());
    }

    template <class BidirectionalIter>
    void
    inplace_merge(BidirectionalIter first, BidirectionalIter middle,
                    BidirectionalIter last)
    {
        if (first == middle || middle == last)  // 只有一个区间，不需要操作
            return ;
        mystl::inplace_merge_aux(first, middle, last, value_type(first));
    }

    // 重载版本使用函数对象 comp 代替比较操作
    // 没有缓冲区情况下的合并
    template <class BidirectionalIter, class Distance, class Compare>
    void merge_without_buffer(BidirectionalIter first, BidirectionalIter middle,
                                BidirectionalIter last, Distance len1, Distance len2, 
                                Compare comp)
    {
        if (len1 == 0 || len2 == 0)
            return ;
        if (len1 + len2 == 2)
        {
            if (comp*(middle, *first))
                mystl::iter_swap(first, middle);
            return ;
        }
        auto first_cut = first;
        auto second_cut = middle;
        Distance len11 = 0;
        Distance len22 = 0;
        if (len1 > len2)
        {
            len11 = len1 >> 1;
            mystl::advance(first_cut, len11);
            second_cut = mystl::lower_bound(middle, last, *first_cut, comp);
            len22 = mystl::distance(middle, second_cut);
        }
        else
        {
            len22 = len2 >> 1;
            mystl::advance(second_cut, len22);
            first_cut = mystl::upper_bound(first, middle, *second_cut, comp);
            len11 = mystl::distance(first, first_cut);
        }
        auto new_middle = mystl::rotate(first_cut, middle, second_cut);
        mystl::merge_without_buffer(first, first_cut, new_middle, len11, len22, comp);
        mystl::merge_without_buffer(new_middle, second_cut, last, len1 - len11, len2 - len22, comp);
    }
    
    template <class BidirectionalIter1, class BidirectionalIter2, class Compare>
    BidirectionalIter1
    merge_backward(BidirectionalIter1 first1, BidirectionalIter1 last1,
                    BidirectionalIter2 first2, BidirectionalIter2 last2,
                    BidirectionalIter1 result, Compare comp)
    {
        if (first1 == last1)
            return mystl::copy_backward(first2, last2, result);
        if (first2 == last2)
            return mystl::copy_backward(first1, last1, result);
        --last1;
        --last2;
        while (true)
        {
            if (comp(*last2, *last1))
            {
                *--result = *last1;
                if (first1 == last1)
                    return mystl::copy_backward(first2, ++last2, result);
                --last1;
            }
            else
            {
                *--result = *last2;
                if (first2 == last2)
                    return mystl::copy_backward(first1, ++last1, result);
                --last2;
            }
        }
    }

    // 有缓冲区的情况下合并
    template <class BidirectionalIter, class Distance, class Pointer, class Compare>
    void merge_adaptive(BidirectionalIter first, BidirectionalIter middle, 
                        BidirectionalIter last, Distance len1, Distance len2,
                        Pointer buffer, Distance buffer_size, Compare comp)
    {
        // 区间长度足够放进缓冲区
        if (len1 <= len2 && len1 <= buffer_size)
        {
            Pointer buffer_end = mystl::copy(first, middle, buffer);
            mystl::merge(buffer, buffer_end, middle, last, first, comp);
        }
        else if (len2 <= buffer_size)
        {
            Pointer buffer_end = mystl::copy(middle, last, buffer);
            mystl::merge_backward(first, middle, buffer, buffer_end, last, comp);
        }
        // 区间长度太长，分割递归处理
        else
        {
            auto first_cut = first;
            auto second_cut = middle;
            Distance len11 = 0;
            Distance len22 = 0;
            if (len1 > len2)
            {
                len11 = len1 >> 1;
                mystl::advance(first_cut, len11);
                second_cut = mystl::lower_bound(middle, last, *first_cut, comp);
                len22 = mystl::distance(middle, second_cut);
            }
            else
            {
                len22 = len2 >> 1;
                mystl::advance(second_cut, len22);
                first_cut = mystl::upper_bound(first, middle, *second_cut, comp);
                len11 = mystl::distance(first, first_cut);
            }
            auto new_middle = mystl::rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
                                                        len22, buffer, buffer_size);
            mystl::merge_adaptive(first, first_cut, new_middle, len11, 
                                    len22, buffer, buffer_size, comp);
            mystl::merge_adaptive(new_middle, second_cut, last, len1 - len11,
                                    len2 - len22, buffer, buffer_size, comp);
        }
    }

    template <class BidirectionalIter, class T, class Compare>
    void inplace_merge_aux(BidirectionalIter first, BidirectionalIter middle,
                            BidirectionalIter last, T*, Compare comp)
    {
        auto len1 = mystl::distance(first, middle);
        auto len2 = mystl::distance(middle, last);
        temporary_buffer<BidirectionalIter, T> buf(first, last);
        if (!buf.begin())
            mystl::merge_without_buffer(first, middle, last, len1, len2, comp);
        else   
            mystl::merge_adaptive(first, middle, last, len1, len2, buf.begin(), buf.size(), comp);
    }

    template <class BidirectionalIter, class Compare>
    void inplace_merge(BidirectionalIter first, BidirectionalIter middle, 
                        BidirectionalIter last, Compare comp)
    {
        if (first == middle || middle == last)
            return;
        mystl::inplace_merge_aux(first, middle, last, value_type(first), comp);
    }

    /*****************************************************************************************/
    // partial_sort
    // 对整个序列做部分排序，保证较小的 N 个元素以递增顺序置于[first, first + n)中
    /*****************************************************************************************/
    template <class RandomIter>
    void partial_sort(RandomIter first, RandomIter middle, RandomIter last)
    {
        mystl::make_heap(first, middle);    // 大根堆，first最大
        for (auto i = middle; i < last; ++i)
        {
            // 调换元素，保证在[middle, last]区间内的元素，都要小于*first
            if (*i < *first)
                mystl::pop_heap_aux(first, middle, i, *i, distance_type(first));
        }
        mystl::sort_heap(first, middle);
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class RandomIter, class Compare>
    void partial_sort(RandomIter first, RandomIter middle, RandomIter last, Compare comp)
    {
        mystl::make_heap(first, middle, comp);    // 大根堆，first最大
        for (auto i = middle; i < last; ++i)
        {
            // 调换元素，保证在[middle, last]区间内的元素，都要小于*first
            if (comp(*i, *first))
                mystl::pop_heap_aux(first, middle, i, *i, distance_type(first), comp);
        }
        mystl::sort_heap(first, middle, comp);
    }

    /*****************************************************************************************/
    // partial_sort_copy
    // 行为与 partial_sort 类似，不同的是，把排序结果复制到 result 容器中
    /*****************************************************************************************/
    template <class InputIter, class RandomIter, class Distance>
    RandomIter
    psort_copy_aux(InputIter first, InputIter last, 
                    RandomIter result_first, RandomIter result_last,
                    Distance*)
    {
        if (result_first == result_last)
            return result_last;
        auto result_iter = result_first;
        while (first != last && result_iter != result_last)
        {
            *result_iter = *first;
            ++result_iter;
            ++first;
        }
        mystl::make_heap(result_first, result_iter);
        while (first != last)
        {
            // 此时的first指针，已经向后移动了mystl::distance(result_first, result_last)
            if (*first < *result_first)
                // 把后面更小的元素，替换到前面
                mystl::adjust_heap(result_first, static_cast<Distance>(0),
                                    result_iter - result_first, *first);
            ++first;
        }
        mystl::sort_heap(result_first, result_iter);
        return result_iter;
    }

    template <class InputIter, class RandomIter>
    RandomIter
    partial_sort_copy(InputIter first, InputIter last, 
                        RandomIter result_first, RandomIter result_last)
    {
        return mystl::psort_copy_aux(first, last, result_first, result_last,
                                        distance_type(result_first));
    }

    // 重载版本使用函数对象 comp 代替比较操作
    template <class InputIter, class RandomIter, class Distance, class Compare>
    RandomIter
    psort_copy_aux(InputIter first, InputIter last, 
                    RandomIter result_first, RandomIter result_last,
                    Distance*, Compare comp)
    {
        if (result_first == result_last)
            return result_last;
        auto result_iter = result_first;
        while (first != last && result_iter != result_last)
        {
            *result_iter = *first;
            ++result_iter;
            ++first;
        }
        mystl::make_heap(result_first, result_iter, comp);
        while (first != last)
        {
            // 此时的first指针，已经向后移动了mystl::distance(result_first, result_last)
            if (comp(*first, *result_first))
                // 把后面更小的元素，替换到前面
                mystl::adjust_heap(result_first, static_cast<Distance>(0),
                                    result_iter - result_first, *first, comp);
            ++first;
        }
        mystl::sort_heap(result_first, result_iter, comp);
        return result_iter;
    }

    template <class InputIter, class RandomIter, class Compare>
    RandomIter
    partial_sort_copy(InputIter first, InputIter last,
                        RandomIter result_first, RandomIter result_last, Compare comp)
    {
        return mystl::psort_copy_aux(first, last, result_first, 
                                        result_last, distance_type(result_first), comp);
    }

    /*****************************************************************************************/
    // partition
    // 对于区间内的原重排，被一元条件运算判定为 true 的元素， 放到区间的前段
    // 该函数不保证元素的原始相对位置
    /*****************************************************************************************/
    template <class BidirectionalIter, class UnaryPredicate>
    BidirectionalIter
    partition(BidirectionalIter first, BidirectionalIter last,
                UnaryPredicate unary_pred)
    {
        while (true)
        {
            while (first != last && unary_pred(*first))     // 满足条件
                ++first;
            if (first == last)
                break;
            --last;
            while (first != last && !unary_pred(*last))    // 不满足条件
                --last;
            if (first == last)
                break;
            mystl::iter_swap(first, last);
            ++first;
        }
        return first;
    }

    /*****************************************************************************************/
    // partition_copy
    // 与partition类似，需要将满足一元条件的元素放到 result_true 的输出区间
    // 不满足条件的放到 result_false 的输出区间并返回一个 mystl::pair指针指向这两个区间的尾部
    /*****************************************************************************************/
    template <class InputIter, class OutputIter1, class OutputIter2, class UnaryPredicate>
    mystl::pair<OutputIter1, OutputIter2>
    partition_copy(InputIter first, InputIter last, 
                    OutputIter1 result_true, OutputIter2 result_false,
                    UnaryPredicate unary_pred)
    {
        for ( ; first != last; ++first)
        {
            if (unary_pred(*first))
                *result_true++ = *first;
            else
                *result_false++ = *first;
        }
        return mystl::pair<OutputIter1, OutputIter2>(result_true, result_false);
    }

    /*****************************************************************************************/
    // sort
    // 将[first, last)内的元素递增排序
    /*****************************************************************************************/
    constexpr static size_t kSmallSectionSize = 128;    // 小型区间的大小，在这个区间内采用插入排序
                                                        // 用于控制分割恶化的情况
    template <class Size>
    Size slg2(Size n)
    {
        // 找出logk <= n 的 k 的最大值
        Size k = 0;
        for ( ; n > 1; n >> 1)
            ++k;
        return k;
    }

    // 分割函数 unchecked_partition
    template <class RandomIter, class T>
    RandomIter
    unchecked_partition(RandomIter first, RandomIter last, const T& pivot)
    {
        while (true)
        {
            while (*first < pivot)
                ++first;
            --last;
            while (pivot < *last)
                --last;
            if (!(first < last))
                return first;
            mystl::iter_swap(first, last);
            ++first;
        }
    }

    // 内省式排序，先进行 quick sort，当分割行为有恶化倾向时， 改用 heap sort
    template <class RandomIter, class Size>
    void intro_sort(RandomIter first, RandomIter last, Size depth_limit)
    {
        while (static_cast<size_t>(last - first) > kSmallSectionSize)
        {
            if (depth_limit == 0)
            {
                // 达到最大分割限度
                mystl::partial_sort(first, last, last); // 改用 heap sort
                return ;
            }
            --depth_limit;
            // quick sort
            auto mid = mystl::median(*(first), *(first + (last - first) / 2), *(last - 1));
            auto cut = mystl::unchecked_partition(first, last, mid);
            mystl::intro_sort(cut, last, depth_limit);
            last = cut;    // 下一个循环将进入前半段的 intro_sort
        }
    }

    // 插入排序辅助函数
    template <class RandomIter, class T>
    void unchecked_linear_insert(RandomIter last, const T& value)
    {
        // 寻找 value 插入的位置
        auto next = last;
        --next;
        while (value < *next)
        {
            *last = *next;
            last = next;
            --next;
        }
        *last = value;
    }

    // 不完整的 insterion sort 
    template <class RandomIter>
    void unchecked_insertion_sort(RandomIter first, RandomIter last)
    {
        for (auto i = first; i != last; ++i)
        {
            mystl::unchecked_linear_insert(i, *i);
        }
    }

    // 插入排序 insertion sort
    template <class RandomIter>
    void insertion_sort(RandomIter first, RandomIter last)
    {
        if (first == last)
            return;
        for (auto i = first + 1; i != last; ++i)
        {
            auto value = *i;
            if (value < *first)
            {
                // 当前判断元素小于第一个元素，
                // 进行 [(first, currnet - 1), current] --> [current, (first, current -1)]的整体移动
                mystl::copy_backward(first, i, i+1);
                *first = value;
            }
            else
                // 按照普通的做法，寻找应该插入的位置
                mystl::unchecked_linear_insert(i, value);
        }
    }

    // 完整的插入排序 final_insertion_srot
    template <class RandomIter>
    void final_insertion_sort(RandomIter first, RandomIter last)
    {
        // 根据 待排序空间 的内存大小，选择不同的排序策略
        if (static_cast<size_t>(last - first) > kSmallSectionSize)
        {
            mystl::insertion_sort(first, first + kSmallSectionSize);
            mystl::unchecked_insertion_sort(first + kSmallSectionSize, last);
        }
        else
        {
            mystl::insertion_sort(first, last);
        }
    }

    // 最终的STL排序算法：
    // 将大区间分割为很多小区间，小区间内根据分割度选个 quick sort 或者 heap sort
    // 小区间之间，采用 insertion sort
    template <class RandomIter>
    void sort(RandomIter first, RandomIter last)
    {
        if (first != last)
        {
            // 省内式排序，将待排序区间分为一个个小区间，进行整体的插入排序
            mystl::intro_sort(first, last, slg2(last - first) * 2);
            mystl::final_insertion_sort(first, last);
        }
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class RandomIter, class T, class Compare>
    RandomIter
    unchecked_partition(RandomIter first, RandomIter last, 
                        const T& pivot, Compare comp)
    {
        while (true)
        {
            while (comp(*first, pivot))
                ++first;
            --last;
            while (comp(pivot, *last))
                --last;
            if (!(first < last))
                return first;
            mystl::iter_swap(first, last);
            ++first;
        }
    }

    // 省内式排序，先进行 quick sort，当分割行为有恶化倾向时，改用 heap sort
    template <class RandomIter, class Size, class Compare>
    void intro_srot(RandomIter first, RandomIter last, Size depth_limit, Compare comp)
    {
        while (static_cast<size_t>(last - first) > kSmallSectionSize)
        {
            if (depth_limit == 0)
            {
                mystl::partial_sort(first, last, last, comp);
                return;
            }
            depth_limit--;
            auto mid = mystl::median(*first, *(first + (last - first) / 2), *(last - 1));
            auto cut = mystl::unchecked_partition(first, last, mid, comp);
            mystl::intro_sort(cut, last, depth_limit, comp);
            last = cut;
        }
    }

    // 插入排序辅助函数
    template <class RandomIter, class T, class Compare>
    void unchecked_linear_insert(RandomIter last, const T& value, Compare comp)
    {
        auto next = last;
        --next;
        // 从尾部开始寻找第一个可以插入的位置
        while (comp(value, *next))
        {
            *last = *next;
            last = next;
            --next;
        }
        *last = value;
    }

    // 插入排序
    template <class RandomIter, class Compare>
    void unchecked_insertion_sort(RandomIter first, RandomIter last, Compare comp)
    {
        for (auto i = first; i != last; ++i)
        {
            mystl::unchecked_linear_insert(i, *i, comp);
        }
    }

    // 插入排序函数
    template <class RandomIter, class Compare>
    void insertion_sort(RandomIter first, RandomIter last, Compare comp)
    {
        if (first == last)
            return;
        for (auto i = first + 1; i != last; ++i)
        {
            auto value = *i;
            if (comp(value, *first))
            {
                mystl::copy_backward(first, i, i+1);
                *first = value;
            }
            else
            {
                mystl::unchecked_linear_insert(i, value, comp);
            }
        }
    }

    // 最终的插入函数
    template <class RandomIter, class Compare>
    void final_insertion_sort(RandomIter first, RandomIter last, Compare comp)
    {
        if (static_cast<size_t>(last - first) > kSmallSectionSize)
        {
            mystl::insertion_sort(first, first + kSmallSectionSize, comp);
            mystl::unchecked_insertion_sort(first + kSmallSectionSize, last, comp);
        }
        else
        {
            mystl::insertion_sort(first, last, comp);
        }
    }

    template <class RandomIter, class Compare>
    void sort(RandomIter first, RandomIter last, Compare comp)
    {
        if (first != last)
        {
            // 省内式排序，将区间分为一个个小区间，然后对整体进行插入排序
            mystl::intro_sort(first, last, slg2(last - first) * 2);
            mystl::final_insertion_sort(first, last, comp);
        }
    }

    /*****************************************************************************************/
    // nth_element
    // 对序列重排，使得所有小于第 n 个元素的元素，出现在他前面，大于他的在他后面
    /*****************************************************************************************/
    template <class RandomIter>
    void nth_element(RandomIter first, RandomIter nth, RandomIter last)
    {
        if (nth == last)
            return;
        while (last - first > 3)
        {
            auto cut = mystl::unchecked_partition(
                first, last, 
                mystl::median(*first, *(first + (last - first) / 2), *(last - 1))
                );
            if (cut <= nth)
                first = cut;
            else  
                last = cut;
        }
        mystl::insertion_sort(first, last);
    }

    // 重载版本，使用函数对象 comp 代替比较操作
    template <class RandomIter, class Compare>
    void nth_element(RandomIter first, RandomIter nth, RandomIter last, Compare comp)
    {
        if (nth == last)
            return;
        while (last - first > 3)
        {
            auto cut = mystl::unchecked_partition(
                first, last, 
                mystl::median(*first, *(first + (last - first) / 2), *(last - 1)), comp
                );
            if (cut <= nth)
                first = cut;
            else
                last = cut;
        }
        mystl::insertion_sort(first, last, comp);
    }

    /*****************************************************************************************/
    // unique_copy
    // 从[first, last) 中将元素复制到 result 上，序列必须有序，如果有重复的元素，只会复制一次
    /*****************************************************************************************/
    // unique_copy_dispatch 的 forward_iterator_tag 版本
    template <class InputIter, class ForwardIter>
    ForwardIter
    unique_copy_dispatch(InputIter first, InputIter last, ForwardIter result, forward_iterator_tag)
    {
        *result = *first;
        while (++first != last)
        {
            if (*result != *first)
                *++result = *first;
        }
        return ++result;
    }

    // unique_copy_dispatch 的 output_iterator_tag 版本
    // 由于 output_iterator 只能进行读操作，所以不能有 *result != *first 这样的操作
    template <class InputIter, class OutputIter>
    OutputIter
    unique_copy_dispatch(InputIter first, InputIter last, 
                        OutputIter result, output_iterator_tag)
    {
        auto value = *first;
        *result = value;
        while (++first != last)
        {
            if (value != *first)
            {
                value = *first;
                *++result = value;
            }
        }
        return ++result;
    }

    template <class InputIter, class OutputIter>
    OutputIter
    unique_copy(InputIter first, InputIter last, OutputIter result)
    {
        if (first == last)
            return result;
        return mystl::unique_copy_dispatch(first, last, result, iterator_category(result));
    }

    // 重载版本，使用函数对象comp代替比较操作
    // unique_copy_dispatch 的 forward_iterator_tag 版本
    template <class InputIter, class ForwardIter, class Compare>
    ForwardIter
    unique_copy_dispatch(InputIter first, InputIter last, ForwardIter result, forward_iterator_tag, Compare comp)
    {
        *result = *first;
        while (++first != last)
        {
            if (!comp(*result, *first))
                *++result = *first;
        }
        return ++result;
    }

    // unique_copy_dispatch 的 output_iterator_tag 版本
    // 由于 output_iterator 只能进行读操作，所以不能有 *result != *first 这样的操作
    template <class InputIter, class OutputIter, class Compare>
    OutputIter
    unique_copy_dispatch(InputIter first, InputIter last, 
                        OutputIter result, output_iterator_tag, Compare comp)
    {
        auto value = *first;
        *result = value;
        while (++first != last)
        {
            if (!comp(value, *first))
            {
                value = *first;
                *++result = value;
            }
        }
        return ++result;
    }

    template <class InputIter, class OutputIter, class Compare>
    OutputIter
    unique_copy(InputIter first, InputIter last, OutputIter result, Compare comp)
    {
        if (first == last)
            return result;
        return mystl::unique_copy_dispatch(first, last, result, iterator_category(result), comp);
    }

    /*****************************************************************************************/
    // unique
    // 移除[first, last)内重复的元素，序列必须有序，和remove类似，他并不是正真的删除重复元素
    /*****************************************************************************************/
    template <class ForwardIter>
    ForwardIter unique(ForwardIter first, ForwardIter last)
    {
        first = mystl::adjacent_find(first, last);
        return mystl::unique_copy(first, last, first);
    }

    // 重载版本，使用函数对象comp代替比较操作
    template <class ForwardIter, class Compare>
    ForwardIter unique(ForwardIter first, ForwardIter last, Compare comp)
    {
        first = mystl::adjacent_find(first, last, comp);
        return mystl::unique_copy(first, last, first, comp);
    }

    
} // namespace mystl

#ifdef _MSC_VER
#pragma warning(pop)
#endif

#endif